package SlidingWindow;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @ClassName LC30
 * @Description TODO
 * @Author ZJX
 * @Date 2024/9/20 14:19
 * @Version 1.0
 */

public class LC30 {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();

        // 保存字典中所有单词的频次
        Map<String, Integer> hash1 = new HashMap<>();
        for (String word : words) {
            hash1.put(word, hash1.getOrDefault(word, 0) + 1);
        }

        int len = words[0].length(); // 每个单词的长度
        int m = words.length; // 单词的数量

        // 通过不同起点进行滑动窗口处理
        for (int i = 0; i < len; i++) {
            Map<String, Integer> hash2 = new HashMap<>(); // 保存窗口内所有单词的频次
            int left = i, right = i, count = 0; // 窗口边界和匹配计数器

            // 右边界逐步扩展窗口
            while (right + len <= s.length()) {
                // 将新单词加入窗口
                String inWord = s.substring(right, right + len);
                right += len;

                // 检查该单词是否在 words 中
                if (hash1.containsKey(inWord)) {
                    hash2.put(inWord, hash2.getOrDefault(inWord, 0) + 1);
                    if (hash2.get(inWord) <= hash1.get(inWord)) {
                        count++;
                    }
                }

                // 窗口长度超出，需要从左边移除单词
                while (right - left > len * m) {
                    String outWord = s.substring(left, left + len);
                    left += len;

                    if (hash1.containsKey(outWord)) {
                        if (hash2.get(outWord) <= hash1.get(outWord)) {
                            count--;
                        }
                        hash2.put(outWord, hash2.get(outWord) - 1);
                    }
                }

                // 如果匹配到所有单词，记录起始位置
                if (count == m) {
                    ret.add(left);
                }
            }
        }

        return ret;
    }

}
